Mapping of, and localization within, an environment is critical for efficient and effective robot exploration and navigation. Mapping is useful for identifying features of the environment that can increase or hinder the objectives of the mobile robot. To function most effectively, mobile robots need to discover the properties of the physical environment they are located in. Knowing details of the location can assist navigation, communication, and object retrieval or placement. For example, identification of corners or intersections of hallways within an indoor environment is useful for surveillance and networking applications. Additionally, knowledge of whether a robot has previously traversed an area aids in maximizing battery life and minimizing time of exploration. Further, mapping the physical environment can help determine the size of the area explored by the robot, and, if the robot gets stuck or otherwise blocked by an obstacle, allows the robot to return to a known, higher value area.
Generally, mobile robots use self-contained on-board guidance systems, which can include environmental sensors to track relative movement, detect collisions, identify obstructions, or provide awareness of the immediate surroundings. Sensor readings are used to plan the next robotic movement or function to be performed. Movement can occur in a single direction or could be a sequence of individual movements, turns, and stationary positions.
Mapping of an environment can often consist of, or even require, multiple maps, each with possibly different characteristics or obtained through diverse techniques. For example, a global, or large, map such as a floor plan from building design may be given as prior knowledge or obtained by manual surveying. Conversely, a local, or small, map can be obtained from mobile robot exploration and sensing. The global and one or more local maps often need to be aligned. Map alignment is important to robot navigation as a stepping stone to a number of essential capabilities such as localization, loop detection, and map merging.
For example, by aligning a local map obtained by robot navigation with a global map, the location of the robot within the environment can be determined. Additionally, loop detection allows a robot to recognize repetitions in trajectory, which can be used to refine the map and improve mapping accuracy. Moreover, loop detection can prevent the robot from wasting energy traversing areas again that have already been explored. Furthermore, two or more robots may have built maps representing the part of an environment that they have each visited. Map alignment facilitates merging of the individual maps of each robot into a coherent larger map.
Conventional modes of mapping of a physical environment by robots include using a comprehensive sensor suite with long-range sensors, such as cameras, ultrasonic rangers, and light detection and ranging (LIDAR) to detect obstacles in front of, or surrounding, the robot. Long-range measurement of the environment has a large overhead, both economically due to the high cost of components, and efficiency, due to high power demands. Additionally, high-level computer cognitive models are used for environment mapping but incur a high computational overhead that often requires external, and time delayed, computation. These requirements for sensor-rich robots and powerful computation can be beyond the capabilities low-power robots with short-range sensors.
Therefore, there is a need for an approach to map alignment that is both cost-effective and efficient. Preferably, such an approach will be robust against reading noise, created by sensor misreadings and other errors.